package com.heima.algorithm.sort;

/**
 * <strong>插入排序</strong>
 * <p>思想：默认第一个元素是排好序的，后面依次插入遍历到的元素</p>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/28 19:47
 */
public class InsertionSort {
    //（1）基于比较的排序算法
    //（2）最好情况：O(n)，最坏情况：O(n^2)，平均情况：O(n^2)，空间复杂度：O(1)，稳定：是
    //（3）插入排序非常适合处理小规模的数据排序，这点很重要
    //（4）插入排序对于近乎有序的数据处理速度比较快，复杂度有所下降，可以提前结束

    /**
     * 插入排序非递归实现，递归实现请见{@link com.heima.algorithm.recursion.InsertionSort}
     * @param arr 待排序数组
     */
    public static void insertionSort(int[] arr){
        // 从第二个元素开始依次选择往前插入
        for (int i = 1; i < arr.length; i++){
            int inserted = arr[i];
            // 找到插入位置
            int index = i;
            // index记录当前插入位置，若前一个位置大于待插入元素，则将前一个元素后移，直到小于等于或者index为0
            while (index > 0 && arr[index - 1] > inserted){
                arr[index] = arr[index - 1];
                index--;
            }
            // 如果找到的插入位置不是i再插入
            if (index != i){
                arr[index] = inserted;
            }
        }
    }
}
